import javax.swing.tree.TreeNode;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

//TIP 要<b>运行</b>代码，请按 <shortcut actionId="Run"/> 或
// 点击装订区域中的 <icon src="AllIcons.Actions.Execute"/> 图标。
public class MainTree {
    public static void main(String[] args) {
        //TIP 当文本光标位于高亮显示的文本处时按 <shortcut actionId="ShowIntentionActions"/>
        // 查看 IntelliJ IDEA 建议如何修正。
        System.out.printf("Hello and welcome!");

        for (int i = 1; i <= 5; i++) {
            //TIP 按 <shortcut actionId="Debug"/> 开始调试代码。我们已经设置了一个 <icon src="AllIcons.Debugger.Db_set_breakpoint"/> 断点
            // 但您始终可以通过按 <shortcut actionId="ToggleLineBreakpoint"/> 添加更多断点。
            System.out.println("i = " + i);
        }
    }
}

class Solution1 {
    List<Integer> list = new ArrayList<>();

    public List<Integer> preorderTraversal(TreeNode root) {
        list.add(root.val);
        preTraversal(root.left);
        preTraversal(root.right);
        return list;
    }

    public void preTraversal(TreeNode root) {
        list.add(root.val);
        preTraversal(root.left);
        preTraversal(root.right);
    }
}

class Solution2 {
    LinkedList<List<Integer>> list = new LinkedList<List<Integer>>();

    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null)
            return list;
        start(root);
        return list;
    }

    private void start(TreeNode root) {
        if (root == null)
            return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> list1 = new ArrayList<>();
            int len = queue.size();
            while (len > 0) {
                TreeNode tmp = queue.poll();
                list1.add(tmp.val);
                len--;
                if (tmp.left != null) queue.offer(tmp.left);
                if (tmp.right != null) queue.offer(tmp.right);
            }
            list.addFirst(list1);
        }
    }
}

class Solution3 {
    LinkedList<List<Integer>> list = new LinkedList<List<Integer>>();

    public List<List<Integer>> rightSideView(TreeNode root) {
        if (root == null)
            return list;
        start(root);
        return list;
    }

    private void start(TreeNode root) {
        if (root == null)
            return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int len = queue.size();
            while (len > 0) {
                TreeNode tmp = queue.poll();
                if (len == 1)
                    list.add(tmp.val);
                len--;
                if (tmp.left != null) queue.offer(tmp.left);
                if (tmp.right != null) queue.offer(tmp.right);
            }
        }
    }
}

class Solution4 {
    List<Double> list = new ArrayList<>();

    public List<Double> averageOfLevels(TreeNode root) {
        if (root == null)
            return list;
        start(root);
        return list;
    }

    private void start(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int len = queue.size();
            int total = len;
            double sum = 0;
            while (len > 0) {
                TreeNode tmp = queue.poll();
                len--;
                sum += tmp.val;
                if (tmp.left != null) {
                    queue.offer(tmp.left);
                }
                if (tmp.right != null) {
                    queue.offer(tmp.right);
                }
            }
            list.add(sum / total);
        }
    }
}

class Node {
    public int val;
    public List<Node> children;

    public Node() {
    }

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};

class Solution5 {
    List<List<Integer>> list = new ArrayList<>();

    public List<List<Integer>> levelOrder(Node root) {
        if (root == null)
            return list;
        start(root);
        return list;
    }

    private void start(Node root) {
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int len = queue.size();
            List<Integer> list1 = new ArrayList<>();
            while (len > 0) {
                Node root1 = queue.poll();
                len--;
                list1.add(root1.val);
                if (root1.children != null) {
                    for (int i = 0; i < root1.children.size(); i++) {
                        queue.offer(root1.children.get(i));
                    }
                }
            }
            list.add(list1);
        }
    }
}

class Solution6 {
    List<Integer> list = new ArrayList<>();

    public List<Integer> largestValues(TreeNode root) {
        if (root == null) {
            return list;
        }
        start(root);
        return list;
    }

    private void start(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int len = queue.size();
            int max = Integer.MIN_VALUE;
            while (len > 0) {
                TreeNode root1 = queue.poll();
                len--;
                if (root1.val > max) {
                    max = root1.val;
                }
                if (root1.left != null)
                    queue.offer(root1.left);
                if (root1.right != null)
                    queue.offer(root1.right);
            }
            list.add(max);
        }

    }
}

class Solution7 {
    public int maxDepth(TreeNode root) {
        if (root == null)
            return 0;
        int sum = start(root);
        return sum;
    }

    private int start(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int deep = 0;
        while (!queue.isEmpty()) {
            int len = queue.size();
            deep++;
            while (len > 0) {
                TreeNode node = queue.poll();
                len--;
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        return deep;
    }


}

class Solution8 {
    public int minDepth(TreeNode root) {
        if (root == null)
            return 0;
        int sum = start(root);
        return sum;
    }

    private int start(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int deep = 0;
        while (!queue.isEmpty()) {
            int len = queue.size();
            deep++;
            while (len > 0) {
                TreeNode node = queue.poll();
                len--;
                //如果当前节点的左右孩子都为空，直接返回最小深度
                if (node.left == null && node.right == null) {
                    return deep;
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        return deep;
    }
}

class Solution9 {
    public TreeNode invertTree(TreeNode root) {
        if (root == null)
            return root;
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

class Solution10 {
    public boolean isSymmetric(TreeNode root) {
        return start(root.left, root.right);
    }

    public boolean start(TreeNode root1, TreeNode root2) {
        if (root1 == null & root2 != null)
            return false;
        if (root1 != null & root2 == null)
            return false;
        if (root1 == null & root2 == null)
            return true;
        if (root2.val != root1.val)
            return false;
        boolean res1 = start(root1.left, root2.right);
        boolean res2 = start(root1.right, root2.left);
        return res2 & res1;
    }
}

//class Solution {
//    public int countNodes(TreeNode root) {
//        if(root==null){
//            return 0;
//        }
//        return 1+countNodes(root.left)+countNodes(root.right);
//    }
//
//
//}
class Solution11 {
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return start(root);
    }

    private int start(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int sum = 0;
        while (!queue.isEmpty()) {
            int len = queue.size();
            sum = sum + len;
            while (len > 0) {
                TreeNode node;
                node = queue.poll();
                len--;
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        return sum;
    }
}

class Solution12 {
    boolean status = true;
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        start(root);
        return status;
    }

//    private boolean start1(TreeNode root1,TreeNode root2) {
//        int l = start(root1);
//        int r = start(root2);
//        if (Math.abs(l-r)>1)
//            return false;
//        else return true;
//    }

    public int start(TreeNode node) {
        if (node==null||!status)
            return 0;
        int l = 1+start(node.left);
        int r = 1+start(node.right);
        if (Math.abs(l-r)>1)
            status = false;
        return Math.max(l,r);


    }
}

class Solution13 {
    List<String> list = new ArrayList<>();
    public List<String> binaryTreePaths(TreeNode root) {
        start(root,"");
        return list;
    }

    private void start(TreeNode root, String s) {
        if (root.left==null&&root.right==null){
            list.add(new StringBuilder(s).append(root.val).toString());
            return;
        }
        s = new StringBuilder(s).append(root.val).append("->").toString();
        if(root.left!=null)
            start(root.left,s);
        if(root.right!=null)
            start(root.right,s);
    }
}

//class Solution {
//    public int sumOfLeftLeaves(TreeNode root) {
//        if(root==null)
//            return 0;
//        int l = sumOfLeftLeaves(root.left);
//        int r = sumOfLeftLeaves(root.right);
//        if(root.left!=null&&root.left.left==null&&root.left.right==null){
//            return l+r+root.left.val;
//        }else
//            return l+r;
//    }
//}
class Solution14 {
    int sum = 0;
    public int sumOfLeftLeaves(TreeNode root) {
        if(root==null)
            return 0;
        if(root.left!=null&&root.left.left==null&&root.left.right==null){
            sum+=root.left.val;
        }
        sumOfLeftLeaves(root.left);
        sumOfLeftLeaves(root.right);
        return sum;
    }
}

class Solution15 {
    public int findBottomLeftValue(TreeNode root) {
        return start(root);
    }

    private int start(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int key =0;
        while (!queue.isEmpty()){
            int len = queue.size();
            int first = 1;
            while(len>0){
                TreeNode node = queue.poll();
                if(first==1)
                    key = node.val;
                first=0;
                len--;
                if(node.left!=null)
                    queue.offer(node.left);
                if(node.right!=null)
                    queue.offer(node.right);
            }
        }
        return key;
    }
}

class Solution {
    int target = 0;
    int ex=0;
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root==null)
            return false;
        target = targetSum;
        start(root,0);
        if(ex==1)
            return true;
        else return false;
    }

    private void start(TreeNode root,int sum) {
        if(root==null)
            return ;
        sum+=root.val;
        if(root.left==null&&root.right==null&&sum==target){
            ex = 1;
        }
        System.out.println(sum);
        start(root.left,sum);
        start(root.right,sum);
    }
}